package leetcode_线段树;

/**
 * 将水果装入篮子 III (440 场周赛 T3)
 * 算法: 线段树
 *
 * @author yezh
 * @date 2025/3/9 20:46
 */
public class _3479 {

    class SegmentTree {
        private final int[] max;

        public SegmentTree(int[] a) {
            int n = a.length;
            max = new int[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
            build(a, 1, 0, n - 1);
        }

        public int findFirst(int h, int l, int r, int x) {
            if (max[h] < x) return -1;
            if (l == r) return l;
            int m = (l + r) / 2;
            int i = findFirst(h * 2, l, m, x);
            if (i < 0) i = findFirst(h * 2 + 1, m + 1, r, x);
            return i;
        }

        public void update(int h, int l, int r, int i, int x) {
            if (l == r) {
                // a[l] = max[h], a 中第 l 个位置在 max 中的第 h 个位置
                max[h] = x;
                return;
            }
            int m = (l + r) / 2;
            if (i <= m) update(h * 2, l, m, i, x);
            else update(h * 2 + 1, m + 1, r, i, x);
            maintain(h);
        }

        private void build(int[] a, int h, int l, int r) {
            if (l == r) {
                max[h] = a[l];
                return;
            }
            int m = (l + r) / 2;
            build(a, h * 2, l, m);
            build(a, h * 2 + 1, m + 1, r);
            maintain(h);
        }

        public int findFirstAndUpdate(int o, int l, int r, int x) {
            if (max[o] < x) return -1;
            if (l == r) {
                max[o] = -1;
                return l;
            }
            int m = (l + r) / 2;
            int i = findFirstAndUpdate(o * 2, l, m, x);
            if (i < 0) i = findFirstAndUpdate(o * 2 + 1, m + 1, r, x);
            maintain(o);
            return i;
        }

        private void maintain(int o) {
            max[o] = Math.max(max[o * 2], max[o * 2 + 1]);
        }

    }

    class Solution {
        public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
            SegmentTree st = new SegmentTree(baskets);
            int ans = 0, n = fruits.length;
            for (int fruit : fruits) {
                int i = st.findFirst(1, 0, n - 1, fruit);
                if (i < 0) ++ans;
                else st.update(1, 0, n - 1, i, -1);
                // if (st.findFirstAndUpdate(1, 0, n - 1, fruit) < 0) ++ans;
            }
            return ans;
        }
    }

}
